# 合并二叉树：https://leetcode-cn.com/problems/merge-two-binary-trees/submissions/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        """
            因为可能需要添加结点，所以需要记录前一个父节点，且从根节点开始， 使用前序遍历
        """
        def dfs(node1, node2):
            # 1. 两个都为None， 返回None
            if not node1 and not node2:
                return None     
            
            # 2. 其他情况
            if node1 and node2:
                node = TreeNode(node1.val + node2.val)
            elif node1:
                node = TreeNode(node1.val)
            else:
                node = TreeNode(node2.val)

            node1_left = node1.left if node1 else None
            node2_left = node2.left if node2 else None
            node1_right = node1.right if node1 else None
            node2_right = node2.right if node2 else None

            # 3. 去确定当前节点的左右子节点为啥
            node.left = dfs(node1_left, node2_left)
            node.right = dfs(node1_right, node2_right)
            
            return node

        return dfs(root1, root2)


# 官方简便写法
class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        """
            不需要所有的节点都重新创建
            时间复杂度：O(min(m,n))
            空间复杂度：O(min(m,n))
        """
        if not t1:
            return t2
        if not t2:
            return t1
        
        merged = TreeNode(t1.val + t2.val)
        merged.left = self.mergeTrees(t1.left, t2.left)
        merged.right = self.mergeTrees(t1.right, t2.right)
        return merged

